/**
 * Definition for node.
 * class Node {
 *     val: number
 *     children: Node[]
 *     constructor(val?: number) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.children = []
 *     }
 * }
 */
// 解法1 递归
 function preorder(root: Node | null): number[] {
    if(!root){
        return [];
    }
    const res = [];
    const preorderTraversal = (node:  Node | null):void =>{
        if(!node){
            return;
        }
        res.push(node.val);
        for(let item of node.children){
            preorderTraversal(item);
        }
    }
    preorderTraversal(root);
    return res;
};

// 解法2 迭代法

function preorder1(root: Node | null): number[] {
    if(!root){
        return [];
    }
    const res = [];
    const stack:Node[] = [root]
    while(stack.length){
        const node:Node = stack.pop();
        res.push(node.val);
        // 这里利用栈的原理，先进后出，
        // 对于子节点，前序遍历是从左到右的遍历，
        // 这里我们先把子节点，倒序，然后放入栈中，这样再从栈中取出元素的时候，就能实现从左到右的遍历子节点了
        node.children.reverse();
        for(let item of node.children){
            stack.push(item)
        }
    }
    return res;
};